1. Field of the Invention
The invention is generally directed to digital signal processing. The invention is more specifically directed to a method for carrying out a mixed-radix Fast Fourier Transform.
2. Cross Reference to Related Patents
The following U.S. patent(s) is/are related to the present application and its/their disclosures is/are incorporated herein by reference:
(A) U.S. Pat. No. 5,029,079 issued Jul. 2, 1991 to Magar, et al, and entitled APPARATUS AND METHOD FOR FLEXIBLE CONTROL OF DIGITAL SIGNAL PROCESSING DEVICES.
3. Description of the Related Art
The Fast Fourier Transform (FFT) is a well known algorithm that is used in digital signal processing for transforming a set of N time-domain sample points into a corresponding set of N frequency-domain sample points. FFT processes find utility in a variety of applications, including machine-implemented speech recognition, image enhancement of video or tomography signals, adaptive filtering of digitized waveforms, and so forth.
The basic FFT equations are given below as Eq. 1 and Eq. 2. ##EQU1##
The time-domain samples are represented as x(0) through x(N-1). The frequency-domain components are represented as X(0) through X(N-1).
It is seen from the above Eq. 1 that each frequency-domain component X(k) is a weighted sum of all N time-domain components, x(0)-x(N-1). The weights W.sub.N.sup.ik are referred to as twiddle factors.
Machine implemented computation of an FFT is often simplified by cascading together a series of simple multiply-and-add stages. When a recursive process is used, data circulates through a single stage and the computational structure of the stage is made variable for each circulation. Each circulation through the stage is referred to as a "pass".
A plurality of computational elements, each known as a radix-r butterfly, may be assembled to define a single stage for carrying out a particular pass. A radix-r butterfly receives r input signals and produces a corresponding number of r output signals, where each output signal is the weighted sum of the r input signals. The radix number, r, in essence, defines the number of input components which contribute to each output component.
By way of example, a radix-2 butterfly receives two input signals and produces two output signals. Each output signal is the weighted sum of the two input signals. A radix-3 butterfly receives three input signals and produces three corresponding output signals. Each output signal of the radix-3 butterfly constitutes a weighted sum of the three input signals.
Completion of an N-point Fast Fourier Transform (FFT) requires that the product of the butterfly radix values, taken over the total number of stages or passes, equals the total point count, N. Thus, a 64-point FFT can be performed by one radix-64 butterfly or two cascaded stages where each stage has eight radix-8 butterflies (the product of the radix values for stage-1 and stage-2 is 8.times.8=64) or six cascaded stages where each of the six stages comprises 32 radix-2 butterflies (the product of the radix values for stage-1 through stage-6 is 2.times.2.times.2.times.2.times.2.times.2=64).
It has been shown that a multi-stage or multi-pass FFT processes can be correctly carried out under conditions where the number of butterfly elements changes from one pass (or stage) to the next and the radix value, r, of the butterfly elements also changes from one pass (or stage) to the next. A paper by Gordon DeMuth, "ALGORITHMS FOR DEFINING MIXED RADIX FFT FLOW GRAPHS", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol 37, No. 9, September 1989, Pages 1349-1358, describes a generalized method for performing an FFT with a mixed-radix system. A mixed-radix system is one where the radix value, r, in one stage or pass is different from that of at least one other stage or pass.
An advantage of a mixed-radix computing system is that it can be "tuned" to optimize the signal-to-noise ratio of the transform (or more correctly speaking, to minimize the accumulated round-off error of the total transform) for each particular set of circumstances. By way of example, it may be advantageous in one environment to perform a 64-point FFT using the mixed-radix sequence: 2, 4, 4, 2. In a different environment, it may be more advantageous to use the mixed-radix sequence: 4, 2, 4, 2. Round-off error varies within a machine of finite precision as a function of radix value and the peak signal magnitudes that develop in each stage or pass.
The DeMuth mixed-radix algorithm calls for a particular shuffle of input signals at the first stage of a multi-pass processor. The shuffle is dependent on the specific sequence of radixes used in the mixed-radix system. A 2, 4, 4, 2 radix sequence might use a specific, first input shuffle while a 4, 2, 4, 2 radix sequence uses a completely different, second input shuffle.
The shuffle algorithm described by DeMuth is referred to here and elsewhere as "digit reversal".
Conceptually speaking, digit reversal starts off by ordering the input signals or components in numerical sequence, x(0), x(1), x(2), . . . , x(N-1). The index number, i, of each input component, x(i) is then converted to a binary representation, with the total number of bits used to represent each index value, i, being equal to log.sub.2 N. For the case of N=64=2.sup.6, each index number, i, would be represented by a field of six bits.
Next, each field is subdivided into a plurality of "digits". The number of digits is equal to the number of stages in the multi-pass or multi-stage mixed-radix system. The number of bits used to represent each digit is equal to log.sub.2 r.sub.m, where r.sub.m is the radix value of the corresponding stage-m.
The collection of bits used to define a digit in this manner is referred to here as a "subfield". A one-bit wide subfield defines the corresponding digit of a radix-2 stage. A two-bit wide subfield defines the corresponding digit of a radix-4 stage. A three-bit wide subfield represents the corresponding digit of a radix-8 stage, and so on.
For the case of a mixed-radix sequence, r.sub.1 r.sub.2 r.sub.3 r.sub.4, which is specifically defined by the integer sequence: 2, 4, 4, 2; the product N is 64, and the resulting binary-coded representation of the index value i, is the 6-bit wide, four-digit wide sequence: EQU i.sub.bin =D.sub.4 D.sub.3 D.sub.2 D.sub.1,
where D.sub.4 is one bit wide, D.sub.3 is 2-bits wide, D.sub.2 is 2-bits wide, and D.sub.1 is one bit wide. The symbol r.sub.1 is the radix of stage-1, which is the stage that receives the initial input signals, x(0) through x(N-1).
The above symbol, r.sub.2, is the radix of the second stage which receives the output signals developed by the first stage, and so forth. D.sub.1 is the digit developed for the radix-r.sub.1 stage. D.sub.4 is the digit developed for the radix-r.sub.4 stage. Accordingly, D.sub.4 is defined by the left most (most significant) bit in the 6-bit wide binary-coded field, i.sub.bin =D.sub.4 D.sub.3 D.sub.2 D.sub.1. D.sub.1 is defined by the right most (least significant) bit.
Once this is done, a shuffled index value, i*, is formed simply by reversing the order of digits from a left-to-right order to a right-to-left order. More specifically, in a four-stage system, the shuffled index becomes: EQU i*=D.sub.1 D.sub.2 D.sub.3 D.sub.4
where the reversed digits represent the same set of bits they represented in the original index number, i=D.sub.4 D.sub.3 D.sub.2 D.sub.1. The most significant digit in i* is D.sub.1. The most significant digit in i is D.sub.4.
After digit reversal is performed, input components are presented sequentially to the first stage (or pass) of the multi-stage (or multi-pass) system according to the sequence x(i*) where i* is the digit-reverse transform of the natural sequence i=0, 1, 2, 3, . . . , N-1.
A number of techniques have been proposed for automatically generating digit-reversed sequences. The following papers are representative of the proposed techniques: (a) J. J. Rodriguez, "An Improved FFT Digit-Reversal Algorithm", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 37, No. 8, August 1989, Pages 1298-1300; (b) J. S. Walker, "A New Bit Reversal Algorithm", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 38, No. 8, August 1990, Pages 1472-1473; (c) A. A. Yong, "A Better FFT Bit-Reversal Algorithm Without Tables", IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol. 39, No. 10, October 1991, Pages 2365-2367; and (d) A. Biswas, "Bit Reversal In FFT From Matrix Viewpoint", IEEE Transactions on Signal Processing, Vol. 39, No. 6, June 1991, pages 1415-1418. Generally speaking, machine implementation of the proposed techniques is limited by undue complexity and/or inflexibility and/or slow execution speed.
Recently, a class of high-speed, user-programmable digital signal processor chips (DSP's) have been introduced. The Sharp LH9124 digital signal processor is representative of these devices. It can be programmed to perform single-pass multi-butterfly operations in the radix-2 or radix-4 format.
The utility of such a multi-radix DSP chip can be greatly enhanced if an automated method were provided for shuffling input data for any arbitrary mix of different or identical radix values. Previously known shuffle techniques suffer from limited flexibility and/or slow execution speed.